COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00012 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\def\fnc#1{\mathop{\rm #1}\nolimits}
\rm
\line{\sevenrm a09.tex[154,phy] \today\hfill}

\bigskip\noindent
%{\bf Successive Approximation}

To ``standardize'' a PDA, constructed as a flowchart using these components:

\bigskip
\bigskip
$$\vcenter{\halign{\ctr{#}\qq\qq\qq&\ctr{#}\qq\qq\qq&\ctr{#}\qq\qq\qq\qq&$\ctr{#}$\cr
START\cr
\noalign{\smallskip}
&ACCEPT&REJECT&\bullet\cr}}$$

\vfill

$$\vcenter{\halign{\ctr{#}\q&\ctr{#}\q&\ctr{#}\qq\qq\qq
&\ctr{#}\q&\ctr{#}\q&\ctr{#}\qq\qq\qq&\ctr{#}\cr
&READ&&&EOF?&&WRITE X\cr
\noalign{\bigskip}
a&b&EOF&true&&false\cr}}$$

\vfill

$$\vcenter{\halign{\ctr{#}\qq\qq
&\ctr{#}\q&\ctr{#}\q&\ctr{#}\qq
&\ctr{#}\q&\ctr{#}\q&\ctr{#}\qq
&\ctr{#}\q&\ctr{#}\q&\ctr{#}\cr
PUSH X (0 or 1)&&POP&&&EMPTY?&&&TOP\cr
\noalign{\bigskip}
&0&1&Empty&true&&false&0&1&Empty\cr}}$$

\vfill\eject

\noindent{\bf Stage 1:} Make these replacements.

$$\vcenter{\halign{\ctr{#}\q&\ctr{#}\q&\ctr{#}\qq\qq
&\ctr{#}\q&\ctr{#}\q&\ctr{#}\q&\ctr{#}\q&\ctr{#}\q&\ctr{#}\cr
&Original&&&&&Modified\cr
\noalign{\bigskip\bigskip}
&START&&&&&START\cr
\noalign{\bigskip}
&&&&&&push \#\cr
\noalign{\bigskip\bigskip\bigskip}
&READ&&&&&EOF?\cr
\noalign{\bigskip}
a&b&EOF&&false&&&\phantom{a}&true\cr
\noalign{\bigskip}
&&&&READ\cr
\noalign{\bigskip}
&&&a&&b\cr
\noalign{\bigskip\bigskip\bigskip}
&POP&&&&&POP\cr
\noalign{\bigskip}
0&1&Empty&&0&&1&&\#\cr
\noalign{\bigskip}
&&&&&&&&push \#\cr
\noalign{\bigskip\bigskip\bigskip}
&EMPTY?&&&&&POP\cr
\noalign{\bigskip}
true&&false&&0&&1&&\#\cr
\noalign{\bigskip}
&&&&push 0&&push 1&&push \#\cr
\noalign{\bigskip\bigskip\bigskip}
&TOP&&&&&POP\cr
\noalign{\bigskip}
0&1&Empty&&0&&1&&\#\cr
\noalign{\bigskip}
&&&&push 0&&push 1&&push \#\cr}}$$

\vfill\eject

\noindent{\bf Stage 2:}

Modify so that the PDA never makes a redundant test of EOF.  Make three copies of
the flowchart; which one the program is in depends on whether the value of EOF is
true, false, or unknown.  EOF tests are bypassed if the result is known; if
resulting loops are empty, they are replaced by REJECT.  A~READ enters the region
where EOF is unknown; an EOF enters one of the regions where EOF is known.

\bigskip
\noindent{\bf Stage 3:}

Eliminate a PUSH if it leads, without further PUSHing or branching (branching means
READ or EOF or a non-deterministic choice) to a~POP.

\bigskip\noindent
Example:					

$$\vcenter{\halign{\ctr{#}\qq\qq&\ctr{#}\qq\qq&\ctr{#}\qq&\ctr{#}\qq\qq
&\ctr{#}\qq&\ctr{#}\q&\ctr{#}\q&\ctr{#}\cr
&&&READ\cr
\noalign{\bigskip}
&&&a\cr
\noalign{\bigskip}
PUSH 1&PUSH 0&WRITE A&&WRITE B&&POP\cr
\noalign{\bigskip}
&This one&&&&0&&1\cr
&can be\cr
&eliminated.\cr}}$$

\bigskip\noindent
becomes

\bigskip
$$\vcenter{\halign{\ctr{#}\qq\qq&\ctr{#}\qq\qq&\ctr{#}\qq&\ctr{#}\qq\qq
&\ctr{#}\qq&\ctr{#}\q&\ctr{#}\q&\ctr{#}\cr
&&&READ\cr
\noalign{\bigskip}
&&&a\cr
\noalign{\bigskip}
PUSH 1&\phantom{eliminated.}&WRITE A&&WRITE B&&POP\cr
\noalign{\bigskip}
&&WRITE B&&&0&&1\cr}}$$

\bigskip

Repeat until no longer applicable.  Replace any non-branching loop by REJECT.

\vfill\eject

\noindent{\bf Stage 4:}
Replace ACCEPT by

\bigskip
$$\vcenter{\halign{\ctr{#}\qq\qq&\ctr{#}\qq\qq&\ctr{#}\qq\qq&\ctr{#}\cr
EOF&false&READ&a,b\cr
\noalign{\bigskip\bigskip}
true&POP&0,1\cr
\noalign{\bigskip\bigskip}
&\#&ACCEPT\cr}}$$

\bigskip\bigskip
Similar for REJECT.

\vfill\eject

After Stage 1, the operations used are:

\bigskip
\halign{\qq\qq\qq\lft{#}\cr
START, ACCEPT, REJECT.\cr
READ*, EOF\cr
WRITE\cr
PUSH, POP*\cr}

\bigskip\noindent
where READ* never tries to read with empty input, and POP* never tries to pop
an empty stack.  There is always a \#\ at the bottom of the stack.

After Stage 2, the algorithm, on input of length $N$, never executes READ more than
$N$~times, nor EOF more than $N+1$ times.

Any computation which runs forever must eventually consist entirely of WRITE, PUSH,
and POP.

After Stage 3, if the PDT is deterministic, every PUSH must lead without branching
to a READ, ACCEPT, or REJECT.  At this point, there is no way a computation can
run forever:

\bigskip
\disleft 25pt:
(1):It can't have infinitely many READs or EOFs, as shown above.

\disleft 25pt:
(2):It can't have infinitely many PUSHes, or it would READ infinitely often.

\disleft 25pt:
(3):It can't have infinitely many POPs, or it would be trying to POP an empty stack.

\disleft 25pt:
(4):All that remains is WRITEs; since they don't branch, they must belong, 
eventually, to a non-branching loop, which would have been replaced by REJECT.

\bigskip
So, after Stage 3, a DPDT must terminate.  After Stage 4, a terminating computation
of a PDT must empty the input and stack; a DPDT will always terminate, with input
and stack empty.

If the original automaton was deterministic, we can now just exchange ACCEPT and
REJECT to get a DPDT accepting the complementary language.

If $L$ is a DPDA language, so is its complement, and its complement is therefore,
like~$L$, a~CFL.  Therefore CFL's whose complements are not CFL's, although 
accepted by NPDA's, can't be accepted by DPDA's.  An example of a CFL 
whose complement is not a CFL is the complement of $\{a↑ib↑ic↑i\}$.  
Also, languages accepted by DPDA's have an
unambiguous grammar, so if a language or its complement is inherently ambiguous
(example: $\{a↑ib↑ic↑j\}+\{a↑ib↑jc↑j\}$), the language if not a DCFL.

\vfill\eject\end